package com.atguigu.floyd;

/**
 * @author RuiKnag
 * @create 2021-06-30-19:35
 */
/*
* 弗洛伊德算法
* 用于寻找给定加权图中顶点间最短路径
* 求出各个顶点间最短路径
*
*算法分析：
* 设置顶点vi到顶点vk的最短路径已知为Lik，顶点vj到顶点vk的最短路径已知为Lkj，顶点vi到顶点vj的最短路径已知为Lij，
* 则vi到vj的最短路径为min(Ljk+Lki,Lij) vk的取值为图中所有顶点，则可获得vi到vj的最短路径
*
*
* */
public class FloydAlgorithm {
    public static void main(String[] args) {
        char[] vertex={'A','B','C','D','E','F','G'};
        final int N=65535;
        int[][] matrix={
                {0,5,7,N,N,N,2},
                {5,0,N,9,N,N,3},
                {7,N,0,N,8,N,N},
                {N,9,N,0,N,4,N},
                {N,N,8,N,0,5,4},
                {N,N,N,4,5,0,6},
                {2,3,N,N,4,6,0}
        };
        Graph graph = new Graph(vertex.length,matrix,vertex);
        graph.show();
        graph.floyd();
        System.out.println("--------------------------------");
        graph.show();
    }

}
class Graph{
    //存放顶点数组
    private char[] vertex;
    //保存，从各个顶点出发到其他顶点的距离，最后的结果，也保留在该数组中
    private int[][] dis;
    //保存到达目标节点的前驱节点
    private int[][] pre;

    public Graph(int length,int[][] matrix,char[] vertex) {
        this.vertex=vertex;
        this.dis=matrix;
        this.pre=new int[length][length];
        //对pre初始化
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                pre[i][j]=i;
            }
        }
    }
    //先死pre数组和dis数组
    public void show(){
        char[] vertex={'A','B','C','D','E','F','G'};
        for (int i = 0; i < dis.length; i++) {
            for (int j = 0; j < dis.length; j++) {
                System.out.print(vertex[pre[i][j]]+" ");
            }
            System.out.println();
            for (int j = 0; j < dis.length; j++) {
                System.out.print("("+vertex[i]+"到"+vertex[j]+"的最短路径为"+dis[i][j]+") ");
            }
            System.out.println();
        }
    }
    public void floyd(){
        int len=0;
        //从中间顶点的遍历 就是k {'A','B','C','D','E','F','G'}
        for (int k = 0; k < dis.length; k++) {
            //从i顶点出发 {'A','B','C','D','E','F','G'}
            for (int i = 0; i < dis.length; i++) {
                for (int j = 0; j < dis.length; j++) {
                    len=dis[i][k]+dis[k][j];
                    if (len<dis[i][j]){
                        dis[i][j]=len;
                        pre[i][j]=pre[k][j];//更新前驱节点
                    }
                }
            }
        }
    }
}
